// https://leetcode-cn.com/problems/generate-parentheses/
// 22. 括号生成
/*
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

有效括号组合需满足：左括号必须以正确的顺序闭合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：

输入：n = 1
输出：["()"]
*/
var generateParenthesis = function (n) {
  const res = []
  // 用lRemain记录还可以使用多少个左括号，用rRemain记录还可以使用多少个右括号
  const dfs = (lRemain, rRemain, str) => {
    // 左右括号所剩的数量，str是当前构建的字符串
    if (str.length == 2 * n) {
      // 字符串构建完成
      console.log('--p', lRemain, rRemain, str)
      return res.push(str) // 加入解集
    }
    if (lRemain > 0) {
      // 只要左括号有剩，就可以选它，然后继续做选择（递归）
      console.log('--1', lRemain, rRemain, str)
      dfs(lRemain - 1, rRemain, str + '(')
    }
    if (lRemain < rRemain) {
      // 右括号比左括号剩的多，才能选右括号
      console.log('--2', lRemain, rRemain, str)
      dfs(lRemain, rRemain - 1, str + ')') // 然后继续做选择（递归）
    }
  }

  dfs(n, n, '') // 递归的入口，剩余数量都是n，初始字符串是空串
  return res
}
generateParenthesis(3)
